The description below is enabling for the skilled person in the field but by way of clarification as to the notation in the mathematics presented the following is given by way of background.
Let GF(N) denote a set of N elements, where N is a power of a prime number, with two special elements 0 and 1 representing the additive and multiplicative identities respectively, and two operators addition ‘+’ and multiplication ‘·’. GF(N) defines a finite field, also known as Galois Field, if it forms a commutative ring with identity over these two operators in which every element has a multiplicative inverse.
Finite fields over GF(2m) and m≧2 can be generated with primitive polynomials (PP) of the form p(x)=xm+Σi=0m−1cixi, where ciεGF(2) [1]. For any α,β ε GF(2m), if α and β are in their polynomial basis as α(x)=Σi=0m−1αixi and β(x)=Σi=0m−1βixi, where αi,βiε{0,1} and 0≦i<m, then multiplication over GF(2m) can be defined as w(x)=α(x)·β(x) mod p(x), where p(x) represents the primitive polynomial used to generate the fields [1], [9], [25]. α+β, i.e. addition over GF(2m), is the pairwise EXOR of the terms in the polynomials or the bitwise EXOR of the bit vectors corresponding to α(x) and β(x).
This table shows the addition tables over GF(4).
+01αβ001αβ110βαααβ01ββα10
This table shows the multiplication tables over GF(4).
×01αβ00000101αβα0αβ1β0β1αshows the addition and multiplication tables over GF(4). Here α and β are assumed to be elements in GF(4). For example assume that α(x)=x, and β(x)=x+1. α+β=α(x)+β(x)=x+x+1=1. There is only one primitive polynomial for generating GF(4), which is p(x)=x2+x+1. Now α·β=α(x)·β(x) mod p(x)=x·(x+1)mod x2+x+1=1.
In this application primitive polynomials will be considered in their decimal notation. For example the primitive polynomial p(x)=x3+x+1 in GF(8) can be represented by the bit vector [1,0,1,1], which is 11 in decimal.
The following notation is used. Let IN={0,1, . . . , N−1}, and δ: IN→GF(N) be a one-to-one mapping with δ(0)=0, δ(1)=1 and, without loss of generality, δ(2)=α, δ(3)=β, etc.
Given a variable xi in GF(N) and πiεIN (1≦i≦n, n is the number of inputs), xi can appear in one of the N polarities denoted by xi,πi=xi+δ(πi). Certain polarities require more resources to represent a polynomial than others. As an example, let ƒ(x1,x2)=αx1x2 represent a function in 0-polarity in GF(3), i.e. both x1 and x2 are in 0-polarity (note that xi,0=xi). In another polarity with x1 in 1-polarity and x2 in 2-polarity, replacing x1 with x1,1−1 and x2 with x2,2−δ(2)=x2,2−α and simplifying we get ƒ(x1,x2)=1+x2,2+αx1,1+αx1,1x2,2, which contains more terms in this case. Finding an optimal polarity can be a difficult problem.
Any function over GF(N) can be expanded in its literal based form as ƒ(x1, . . . , xi, . . . , xn)=Σe=0N−1ge(xi)ƒ|xi=δ(e) where ge(xi)=1−[xi−δ(e)]N−1. Here ge(xi) is called a literal over GF(N). This can be viewed as generalization of Shanon's expansion to GF(N). Such a literal based form allows Multiple-Valued Decision Diagram (MDD)-like canonic graph-based representations as shown in FIG. 3.
Here the internal nodes IN represent the variables of expansion, xi in this case, whereas the terminal nodes TN represent the values of the function corresponding to each value of xi represented by the edges. However since the MDDs are defined in MIN-MAX postalgebra, this representation will be called (M)ultiple (O)utput (D)ecision (D)iagram or MODD to distinguish it from the MDDs. There are two MODD reduction rules: (a) If all the N children of a node v point to the same node w, then delete v and connect the incoming edge of v to w. (b) Share equivalent subgraphs. A reduced MODD can be further optimized and normalized based on additional two rules mentioned in “An Efficient Graph Based Representation of Circuits and Calculation of Their Coefficients in Finite Field,” in Proc. Int. Workshop on Logic and Synth. (IWLS'05), California USA, June 2005 pp. 218-225. An MODD which is reduced by all 4 rules will be called a (Z)ero suppressed and (N)ormalized MODD or ZNMODD.
In FIG. 1 there is shown a circuit production system 10 comprising an input 12, a preprocessing computer 14, a look up database 15, a design complier 16 a production plant 18 and communication paths 20.
The input 12 allows for a user to enter polynomials in the form of an input specification over GF(2m) for which a circuit is desired. The input 12 may comprise a keyboard or other conventional input device. It may also comprise a computer which outputs polynomials from previous calculations.
Preprocessing computer 14 may comprise a conventional computer but is configured, such as by use of specific software, to apply the preprocessing steps described below based on the input specification corresponding to polynomials. The computer 14 comprises a processor 22 and a memory, 24. The memory 24 may be preloaded with coefficients for polynomials corresponding to the input specification. Computer 14 is connected to input 12, look up database 15, and complier 16 by communication paths 20.
Look up database 15 comprises a memory such as a hard disk containing data including polynomial coefficients. The database 15 may be part of the Internet.
Design compiler 16 is conventional and takes a net list from the computer 14, preferably in the form of VHDL but could be in any other appropriate code. And produces a circuit design, matching the netlist which is ready for manufacture. Compiler 16 is connected to preprocessing computer 14 and plant 18 by communication paths 20. Complier 16 may be the Synopsis (RTM) design complier or other suitable industrial tool.
Production plant 18 manufactures circuits such as VLSI chips based on the circuit designs.
In use the user or computer inputs polynomials over GF(2m) into input 12, such as in the form of truth-tables or a directed acyclic graph (DAG) based representations of truth-tables or initial net lists. These are then sent via a communication path 20 to preprocessing computer 14. Computer 14 then applies preprocessing steps in accordance with the invention as described below and produces a netlist in VHDL. The netlist is sent to the design compiler 18 via a communication path 20. The design compiler then produces a circuit design matching the VHDL and send this to the production plant 18 via communication path 20. Lastly the production plant 18 manufactures a polynomial circuit matching the design. The produced circuit can then perform the polynomial input by the user or computer.
In FIG. 2 is shown an example of preprocessing steps 50 performed by computer 14.
First at step S52 the initial spec from input 12 is reviewed. Its is determined by computer 14 whether the initial specification is a truth-table or a directed acyclic graph (DAG) based representations of truth-tables or an initial net list, e.g. DAG based representations of the initial specifications as AND-OR PLA or VHDL/verilog net list forms.
At step S54 the computer 14 determines if the coefficients for the required polynomials are available in memory 24 or look up database 15 either in a graph-based form or in terms of a network of adders or multipliers over GF(2m), i.e. in a net list form. If they are not available the computer 14 proceeds to step S56 and if they are it skips straight to step S58.
At step S56 the computer 14 calculates the required coefficients, and moves on to step S58. At step S58 the coefficients that have been calculated or looked up are stored in memory 24 in diagrammatic form. The polynomials are determined by their coefficients and therefore correct determination of coefficients is important.
Next at step S60 if the graph-based representation of the coefficients is given, then the computer 14 performs a graph-based decomposition over GF(2m) to construct the net list of adders and multipliers. Then at step S62 the net list is factorized and optimized and the computer 14 proceeds to step S64.
At step S64 the computer 14 determines the word level of the polynomial/optimized net list. If the net list is not at the bit level i.e. m is greater than one then it moves on to step S68 but if not i.e. it is over GF(2) the computer 14 skips directly to step S72.
At step S68 the computer 14 synthesizes word level blocks with binary logic elements or look up tables (LUTS) to drill down to the bit level. Next at step S70 it is determined whether the coefficient stages need to be returned to. If yes the computer goes back to step S62 but if not it goes back to step S54.
Finally once all of steps S52 to S70 have been completed the necessary number of times (which will either be once for m=1 or twice for m>1) the computer 14 stores the result as a VHDL, or other format, in memory 24 at step S74 and sends this via communication path 20 to the design compiler 16.
Step S56 requires the coefficients are calculated from the initial input DAG from step S52 to be stored in another DAG at step S58 to form the starting point of the synthesis process.
To calculate the coefficients at step S54 conventional methods may be used.
Given a function ƒ(xn,xn−1, . . . , x1) in GF(N) (N is a power of a prime number) and a polarity number t,ƒ can be represented in the following canonical form.ƒ(xn,x−1, . . . , x1)=κ0,t+κ1,t{tilde over (x)}1+κN,t{tilde over (x)}2+ . . . +κi,t{tilde over (x)}jkik{tilde over (x)}jk−1ik−1 . . . {tilde over (x)}j1i1+ . . . +κNn−1,t{tilde over (x)}nN−1{tilde over (x)}n−1N−1 . . . {tilde over (x)}1N−1.
Here κi,t represents the coefficient of the ith term containing k number of variables in polarity number t, where both i and t are defined in the radix-N number system as i=ikNjk+ik−1Njk−1+ . . . +i1Nj1 and t=πnNn−1+πn−1Nn−2+ . . . +π1.
Further, each πq represents the polarity of the variable xq and 1≦q≦n, i.e. xq,πq=xq+δ(πq). Here {tilde over (x)}l represents the fact that xl is in any one of the polarities {0,1, . . . , N−1}, as determined by t. For example the term associated with the coefficient is κi,t is {tilde over (x)}jkik{tilde over (x)}jk−1ik−1 . . . {tilde over (x)}j1i1, where the polarity of each variable is determined by t.
In many cases the MODD (or MDD) may be available as a part of existing resources during a synthesis, verification or simulation process, in which case the coefficients can be derived from the graphs by means of a known efficient path oriented technique such as is known. We call this technique ‘CompByPath’.
We have the following.
Theorem 1:
Let ƒ(xn,xn−1, . . . , x1) represent an n variable function in GF(N). Its ith coefficient corresponding to a term containing k number of variables in the polarity number t is
                                          κ                          i              ,              t                                =                                                    (                                  -                  1                                )                            k                        ⁢                                          ∑                                                      x                                          j                      k                                                        =                                      δ                    ⁡                                          (                      0                      )                                                                                        δ                  ⁡                                      (                                          N                      -                      1                                        )                                                              ⁢                                                ∑                                                            x                                                                        j                          k                                                -                        1                                                              =                                          δ                      ⁡                                              (                        0                        )                                                                                                  δ                    ⁡                                          (                                              N                        -                        1                                            )                                                                      ⁢                                                                  ⁢                                  …                  ⁢                                                                          ⁢                                                            ∑                                                                        x                                                      j                            1                                                                          =                                                  δ                          ⁡                                                      (                            0                            )                                                                                                                      δ                        ⁡                                                  (                                                      N                            -                            1                                                    )                                                                                      ⁢                                                                                            θ                                                      i                            ,                            t                                                                          ⁡                                                  (                                                                                                                    x                                ~                                                            1                                                        ,                                                                                          x                                ~                                                            2                                                        ,                            …                            ⁢                                                                                                                  ,                                                                                          x                                ~                                                            n                                                                                )                                                                    ⁢                                              f                        ⁡                                                  (                                                                                    x                                                              j                                k                                                                                      ,                                                          x                                                              j                                                                  k                                  -                                  1                                                                                                                      ,                            …                            ⁢                                                                                                                  ,                                                          x                                                              j                                1                                                                                      ,                                                          -                                                              δ                                ⁡                                                                  (                                                                      π                                    l                                                                    )                                                                                                                      ,                                                          -                                                              δ                                ⁡                                                                  (                                                                      π                                                                          l                                      -                                      1                                                                                                        )                                                                                                                      ,                            …                            ⁢                                                                                                                  ,                                                          -                                                              δ                                ⁡                                                                  (                                                                      π                                    1                                                                    )                                                                                                                                              )                                                                                                                                                        ,                            (        1        )            where δ(πl),δ(πl−1), . . . , δ(π1) are the polarities of the variables xl,xl−1, . . . , x1 as determined by t.
Here θi,t is defined in “A Theory of Galois Switching Functions” IEEE Trans. Comp., vol. C-27, no. 3 pp. 239-249, March 1978. In Eq. (1) those variables which are assigned any value will be called assigned variables, and those that have not been will be called unassigned variables.
The complexity of Algorithm CompByPath is associated with (i) the number of paths which do not terminate into a 0-terminal node in the MODD or ZNMODD, and (ii) the number of missing unassigned variables in the path. It has been observed that for most benchmarks the algorithm found the coefficients quickly. Application of this algorithm for determining all the coefficients in large fields can render the process slow. A far more efficient technique is proposed below.
Speeding-Up in Large Fields:
Let the partial coefficient (PC) be defined as
                                                        PC                              i                ,                t                                      ⁡                          (                                                                    x                    ~                                                        j                    k                                                        i                    k                                                  ⁢                                                      x                    ~                                                        j                                          k                      -                      1                                                                            i                                          k                      -                      1                                                                      ⁢                                                                  ⁢                …                ⁢                                                                  ⁢                                                      x                    ~                                                        j                    1                                                        i                    1                                                              )                                =                                                    θ                                  i                  ,                  t                                            ⁡                              (                                                                            x                      ~                                        1                                    ,                                                            x                      ~                                        2                                    ,                  …                  ⁢                                                                          ,                                                            x                      ~                                        n                                                  )                                      ⁢                          f              ⁡                              (                                                      x                                          j                      k                                                        ,                                      x                                          j                                              k                        -                        1                                                                              ,                  …                  ⁢                                                                          ,                                      x                                          j                      1                                                        ,                                      -                                          δ                      ⁡                                              (                                                  π                          l                                                )                                                                              ,                                      -                                          δ                      ⁡                                              (                                                  π                                                      l                            -                            1                                                                          )                                                                              ,                  …                  ⁢                                                                          ,                                      -                                          δ                      ⁡                                              (                                                  π                          1                                                )                                                                                            )                                                    ⁢                                  ⁢                  Then          ⁢                                          ⁢                      Eq            .                                                  ⁢                          (              1              )                                ⁢                                          ⁢          becomes                ⁢                                  ⁢                                  ⁢                                  ⁢                                            κ                              i                ,                t                                      =                                                            (                                      -                    1                                    )                                k                            ⁢                                                ∑                                                            x                                              j                        k                                                              =                                          δ                      ⁡                                              (                        0                        )                                                                                                  δ                    ⁡                                          (                                              N                        -                        1                                            )                                                                      ⁢                                                      ∑                                                                  x                                                  j                                                      k                            -                            1                                                                                              =                                              δ                        ⁡                                                  (                          0                          )                                                                                                            δ                      ⁡                                              (                                                  N                          -                          1                                                )                                                                              ⁢                                                                          ⁢                                      …                    ⁢                                                                                  ⁢                                                                  ∑                                                                              x                                                          j                              1                                                                                =                                                      δ                            ⁡                                                          (                              0                              )                                                                                                                                δ                          ⁡                                                      (                                                          N                              -                              1                                                        )                                                                                              ⁢                                                                        PC                                                      i                            ,                            t                                                                          ⁡                                                  (                                                                                                                    x                                ~                                                                                            j                                k                                                                                            i                                k                                                                                      ⁢                                                                                          x                                ~                                                                                            j                                                                  k                                  -                                  1                                                                                                                            i                                                                  k                                  -                                  1                                                                                                                      ⁢                                                                                                                  ⁢                            …                            ⁢                                                                                                                  ⁢                                                                                          x                                ~                                                                                            j                                1                                                                                            i                                1                                                                                                              )                                                                                                                                                  ,                                    (        2        )            
Lemma 1:
Let κi,t and κi,t be the coefficients corresponding to the two terms {tilde over (x)}jkik{tilde over (x)}jk−1ik−1 . . . {tilde over (x)}j1i1 and {tilde over (x)}jki′k{tilde over (x)}jk−1i′k−1 . . . {tilde over (x)}j1i′1 respectively. Also let i>i′ and il≦i′l for 1≦l≦k. Then κi′,t can be computed from κi,t by multiplying the PCs of κi,t by each value of {tilde over (x)}jkik−i′k{tilde over (x)}jkik−1−i′k−1 . . . {tilde over (x)}j1i1−i′1 and then adding them together without revisiting the ZNMODD (MODD), i.e.
      κ                  i        ′            ,      t        =                    (                  -          1                )            k        ⁢                  ∑                              x                          j              k                                =                      δ            ⁡                          (              0              )                                                δ          ⁡                      (                          N              -              1                        )                              ⁢                        ∑                                    x                                                j                  k                                -                1                                      =                          δ              ⁡                              (                0                )                                                          δ            ⁡                          (                              N                -                1                            )                                      ⁢                                  ⁢                  …          ⁢                                          ⁢                                    ∑                                                x                                      j                    1                                                  =                                  δ                  ⁡                                      (                    0                    )                                                                              δ                ⁡                                  (                                      N                    -                    1                                    )                                                      ⁢                                                                                PC                                          i                      ,                      t                                                        ⁡                                      (                                                                                            x                          ~                                                                          j                          k                                                                          i                          k                                                                    ⁢                                                                        x                          ~                                                                          j                                                      k                            -                            1                                                                                                    i                                                      k                            -                            1                                                                                              ⁢                                                                                          ⁢                      …                      ⁢                                                                                          ⁢                                                                        x                          ~                                                                          j                          1                                                                          i                          1                                                                                      )                                                  ·                                                      x                    ~                                                        j                    k                                                                              i                      k                                        -                                          i                      k                      ′                                                                                  ⁢                                                x                  ~                                                  j                  k                                                                      i                                          k                      -                      1                                                        -                                      i                                          k                      -                      1                                        ′                                                              ⁢                                                          ⁢              …              ⁢                                                          ⁢                                                                    x                    ~                                                        j                    1                                                                              i                      1                                        -                                          i                      1                      ′                                                                      .                                                        
Lemma 1 gives us an opportunity to compute coefficients incrementally without having to visit the ZNMODD each time, i.e. without resorting to Algorithm CompByPath each time.
Let us represent each unassigned variable with 1 and each assigned variable with 0. This results in a set of binary vectors of dimension n. Each position in the binary vector corresponds to whether that particular input variable is assigned or not. The set of all such binary vectors defines a lattice over Boolean algebra. The Greatest Lower Bound (GLB) of this lattice is [00 . . . 0] (i.e. all variables assigned), while the Least Upper Bound (LUB) is [11 . . . 1] (i.e. all variables unassigned). Clearly an n-variable function in GF(N) will have 2n points in the lattice. For GF(2) each point in the lattice will correspond to a single coefficient. However for GF(N) and N>2 each point will correspond to a range of coefficients. For each 1 in the vector corresponding to a point in the lattice, apart from the GLB, the corresponding variable will have N different exponents in the term, ranging from 1 to N−1. Assume that each point in the lattice represents a term having exponents equal to N−1 for all the unassigned variables. If the coefficients of all such terms are known, then the coefficients of all the remaining terms having unassigned variables in the same place can be determined by Lemma 1, without visiting the MODD.
The following example best describes this.